﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace Chuong4
{
    class Logarit
    {
        public Logarit(BigInteger a, BigInteger n, BigInteger b)
        {
            this.A = a;
            this.N = n;
            this.B = b;
        }
        BigInteger x;
        BigInteger a;
        BigInteger b;
        BigInteger n;
        public BigInteger X
        {
            get { return x; }
            set { x = value; }
        }

        public BigInteger N
        {
            get { return n; }
            set { n = value; }
        }

        public BigInteger B
        {
            get { return b; }
            set { b = value; }
        }

        public BigInteger A
        {
            get { return a; }
            set { a = value; }
        }

        // Phương pháp vét cạn
        public void VetCan()
        {
            SoNguyenTo snt = new SoNguyenTo();
            int i = 1;
            while (snt.ModLuyThua(this.A, i, this.N) != B) i++;
            this.X = i;
        }

        //Phương pháp Bayby-step Giant - step
        public void BaybyGiant()
        {
            SoNguyenTo snt = new SoNguyenTo();
            BigInteger b = snt.Random(1, this.N);
            BigInteger m = (BigInteger) Math.Sqrt((double)this.N);
            m++;

            List<BigInteger> list = new List<BigInteger>();
            for (BigInteger j = 0; j < m; j++)
            {
                BigInteger g = snt.ModLuyThua(this.A, j, this.N);
                list.Add(g);
            }

            //Tính khả nghịch a^m
            BigInteger gm_1 = snt.ModLuyThua(Euclid(this.A, this.N), m, this.N);
            //
            BigInteger y = this.B;
            bool check = false;
            for (BigInteger i = 0; i < m; i++)
            {
                for (int j = 0; j < list.Count; j++)
                {
                    if (list[j] == y)
                    {
                        this.X = i * m + j;
                        check = true;
                        break;
                    }
                }
                if (check) break;
                y = (y * gm_1) % N;
            }
        }

        // Phương pháp tính nghịch đảo
        BigInteger y, yy, yyy, r, q;
        public BigInteger Euclid(BigInteger a, BigInteger n)
        {
            BigInteger N = n;
            yy = 0;
            yyy = 1;
            if (a == 1) return 1;
            while (a > 0)
            {
                r = n % a;
                if (r == 0) break;
                q = n / a;
                y = yy - yyy * q;
                n = a;
                a = r;
                yy = yyy;
                yyy = y;
            }
            if (y < 0) return y + N;
            return y;
        }


    }
}
